// https://leetcode.cn/problems/course-schedule/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indegrees(numCourses, 0);

        for (int i = 0; i < prerequisites.size(); i++) {
            indegrees[prerequisites[i][0]]++;
            adj[prerequisites[i][1]].emplace_back(prerequisites[i][0]);
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegrees[i] == 0) {
                q.push(i);
            }
        }

        vector<int> topological;
        while (!q.empty()) {
            int n = q.front();
            q.pop();
            topological.emplace_back(n);

            for (int neighbor : adj[n]) {
                indegrees[neighbor]--;

                if (indegrees[neighbor] == 0) {
                    q.push(neighbor);
                }
            }
        }

        return topological.size() == numCourses;
    }
};